/*
Divide two integers without using multiplication, division and mod operator.
*/

/*
===Notes
   Checklist of number related problem
   1. corner cases (0, 1, ...)
   2. impact of signess (-)
   3. integer overflow issue (use double or long long int)
   4. decide if binary search needs to be used
*/

class Solution {
public:
    int divide(int dividend, int divisor) {
        if (!dividend || divisor == 1) return dividend;
        // translate to positive number
        unsigned long long tmpdiv = llabs(dividend);
        unsigned long long tmpd2, tmpd = llabs(divisor);
        bool negative = (dividend ^ divisor) >> 31;
        int result = 0;
        while (tmpdiv >= tmpd) {
            int tmpres = 1;
            while ((tmpd2 = tmpd << 1) <= tmpdiv) {
                tmpres <<= 1; tmpd = tmpd2;
            }
            result += tmpres;
            tmpdiv -= tmpd;
            tmpd = llabs(divisor);
        }
        return (negative)?(-result):result;
    }
};
